#include <iostream>
#include <math.h>
using namespace std;



struct num{
	string s="1";
	void cac1(){
		char it='0';
		for(int i=s.length()-1;i>=0;i--){
			char l='0';
			if(s[i] >= '5'){
				l = '1';
				s[i] = (s[i]-'0')*2+it-10;
			}
			else{
				s[i] = (s[i]-'0')*2+it;
			}
			it = l;
		}
		if(it == '1'){
			s = "1"+s;
		}
		return;
	}
	
	void cac2(){
		char it='0';
		for(int i=0;i<s.length();i++){
			if((s[i]-'0')%2 == 0){
				s[i] = ((it-'0')*10+s[i]-'0')/2+'0';
				it = '0';
			}
			else{
				s[i] = ((it-'0')*10+s[i]-'0')/2+'0';
				it = '1';
			}
		}
		if(s[0] == '0'  &&  s.length() > 1){
			string l="";
			for(int i=1;i<s.length();i++){
				l += s[i];
			}
			s = l;
		}
		return;
	}
};


int l2(num x){
	int ans=0;
	while(x.s != "1"){
		x.cac2();
		ans++;
	}
	return ans;
}


void p2(int x){
	num ans;
	for(int i=0;i<x;i++){
		ans.cac1();
	}
	cout<<ans.s<<endl;
	return;
}


signed main(){
	int t;
	cin>>t;
	for(int i=0;i<t;i++){
		num x;
		cin>>x.s;
		p2(l2(x));
	}
	return 0;
}
